/*
 * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved.
 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 */

package java.util;

import java.io.IOException;
import java.io.InvalidObjectException;
import java.io.Serializable;
import java.lang.reflect.ParameterizedType;
import java.lang.reflect.Type;
import java.util.function.BiConsumer;
import java.util.function.BiFunction;
import java.util.function.Consumer;
import java.util.function.Function;

/**
 * <p>基于哈希表实现Map接口。
 * 这个实现提供了所有的额外的map操作，并且允许null的value和null的key。
 * （HashMap类与Hashtable大致相同，除了HashMap是非同步的，并且允许null）。
 * 这个类不保证map的顺序，尤其是，他不保证顺序，会随着时间流逝，保持不变。
 * 
 * <p>这个实现为基础操作（get和put）实现了常量时间的性能，假设hash函数将元素均匀地分散到桶中。
 * 对collection视图的迭代需要与HashMap实例的容量（桶的数量）正比的时间，来增加它的大小（key-value映射的数量）。
 * 因此，如果迭代的性能很重要，不要设置初始的容量太大（或者负载因子过小）
 * 
 * <p>HashMap的实例有着两个影响性能的参数：初始capacity和负载因子load factor。
 * capacity是哈希表中桶的数量，初始capacity通常是哈希表创建后的容量。
 * 负载因子load factor是指标，衡量哈希表的容量自动增加时，哈希表有多满。
 * 当哈希表entry的数量，超过了，load factor * 此时的capacity，哈希表重新哈希 rehash
 * （就是内部的数据结构被重构），从而哈希表的桶的数量将近*2
 * 
 * <p>通常来说，默认的load factor 0.75，在时间和空间效率间提供了很好的权衡。
 * 数值更高，会减少空间成本，但是增加了查找的成本（影响了大部分HashMap的操作，包括get和put）。
 * （因为增加负载因子，减少空间成本，就更容易发生hash碰撞，同一个桶的数据更多，查找对应元素时间更长）
 * 设置map的处理容量时，应该考虑map中预期的entry的数量和负载因子，来最小化rehash操作的数量。
 * 如果初始容量大于entry的最大数量/负载因子，不会发生rehash操作
 * 
 * <p>如果许多映射要被存在HashMap实例，使用一个足够大的容量来创建它，
 * 会让映射被存放的更有效率，而不是执行rehash来增大哈希表。
 * 注意：使用许多有着相同的hashcode的key，会降低任何哈希表的效率。
 * 为了改善影响，当key是Comparable的，这个类会使用key之间的比较顺序，来帮助断开连接。
 *
 * <p>注意：这个实现不是同步的。
 * 如果多线程并发地访问一个hashmap，并且至少一个线程结构上修改了map，必须在外部进行同步。
 * （结构上的改变是增加，删除一个或多个元素，
 * 或者显式地改变依赖数组的大小，仅仅改变元素的值不会是一个结构上的改变）
 * 这通常是对将map装入内部的对象进行同步，来完成。
 *
 * <p>如果没有这样的对象，列表应该使用Collections.synchronizedMap来包装它。
 * 它通常该在创建时做，来防止意外对map的非同步访问。<pre>
 *   Map m = Collections.synchronizedMap(new HashMap(...));</pre>
 *
 * <p>这个类所有的集合视图方法，返回的Iterator是快速失败的。
 * 如果Iterator创建后，map在任何时间被结构上改变了，
 * 除了迭代器自己的remove和add方法外，迭代器会抛出ConcurrentModificationException。
 * 因此，面对并发的改变，Iterator快速失败，十分干净，
 * 而不是在将来某个不确定的时间，冒着风险，做任意的，不确定性的操作。
 *
 * <p>注意：不能保证Iterator的快速失败机制，
 * 因为，通常地说，在存在非同步的并发修改的情况下，不可能做出严格的保证。
 * 快速失败的迭代器基于最大努力抛出ConcurrentModificationException。
 * 因此，依赖于这个异常，写程序来保证正确性是错的，
 * 迭代器的快速失败机制，应该仅仅被用来探测bug
 *
 *
 * @param <K> the type of keys maintained by this map
 * @param <V> the type of mapped values
 *
 * @author  Doug Lea
 * @author  Josh Bloch
 * @author  Arthur van Hoff
 * @author  Neal Gafter
 * @see     Object#hashCode()
 * @see     Collection
 * @see     Map
 * @see     TreeMap
 * @see     Hashtable
 * @since   1.2
 */
public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {

    private static final long serialVersionUID = 362498820763181265L;

    /*
     * 实现的说明。
     *
     * 这个map通常作为一个基于桶的哈希表，但如果桶变得过于大，它们被改造为TreeNode的桶，
     * 每个的结构与TreeMap相似。
     * 大多数方法使用通常的桶，但是当可适用时，转发给TreeNode的方法（只需要检查节点的类型）
     * TreeNode的桶可以被遍历，并被像其他的一样使用，但是当桶里的元素过多时，额外地支持更快地查找。
     * 然而，在正常使用时，大多数的桶没有过多的元素，所以在方法中可能会延迟检查tree桶的存在。
     *
     * 树桶，即元素都是TreeNode的桶，通常根据hashcode进行排序，
     * 但是如果两个元素的类都是事先了Comparable接口的类，使用它们的compareTo方法来排序。
     * （我们保守地通过反射，来检查泛型类型来验证这一点——请参见comparableclassFor方法)。
     * 增加了树桶的复杂性是值得的，即使在最坏的情况下，提供O(log n)的性能，
     * 当key有着不同的hashcode或者是可排序的。
     * 因此，当hashCode方法返回的值是低离散分布的，
     * 或者许多key有着同一个hashcode（只要它们也是可比较的），性能优雅地下降。
     * 如果这两种方法都不适用，我们可能浪费2倍的时间和空间。
     * 但目前所知的唯一案例来自于糟糕的用户编程实践，这些实践已经非常缓慢，以至于没有什么区别。)
     * 
     * 因为TreeNode的大小是普通节点的2倍，我们仅仅在桶中有着足够的节点时，
     * 才使用TreeNode，看TREEIFY_THRESHOLD。
     * 并且当数量足够小时（因为删除或者resize），转为普通的桶。
     * 在使用分布良好的hashcode时，很少使用树桶。
     * 理想情况下，在随机的hashcode情况下，桶中节点的数量遵循泊松分布，
     * 默认调整阀值threshold为0.75，平均参数为0.5，
     * 经因为resize的粒度，存在较大差异。
     * 无视差异，预期列表的长度为(exp(-0.5) * pow(0.5, k) /factorial(k))
     *
     * 0:    0.60653066
     * 1:    0.30326533
     * 2:    0.07581633
     * 3:    0.01263606
     * 4:    0.00157952
     * 5:    0.00015795
     * 6:    0.00001316
     * 7:    0.00000094
     * 8:    0.00000006
     * 更多的情况，1000万中少于1次
     *
     * 树桶的root通常是它的第一个节点。
     * 然而，有时（通常仅仅发生于Iterator.remove），
     * root可能是别的，但可以在其他地方通过TreeNode.root()来恢复。
     *
     * 所有适用的内部方法接受hashcode来作为一个参数（通常有public的方法提供），
     * 允许它们来调用它们，而不是重算hashCode。
     * 大多数内部方法也接受一个tab参数，那是当前的哈希表，
     * 但是在调整大小或者转换时，可能是新的或者旧的。
     *
     * 当桶列表被树化，分割或者反树化，我们将它们保持在相同的关联访问/遍历顺序（就是Node.next)，
     * 为了更好地在本地保存，并且稍微简化调用iterator.remove来分割和遍历。
     * 当使用comparator来插入时，为了保持总体的顺序（或者尽可能接近）来保证重新平衡，
     * 我们比较类和identityHashCodes作为tie-breakers
     *
     * 由于子类LinkedHashMap的存在，普通和树模式之间的使用和转换是复杂的。
     * 有关定义在插入、删除和访问时调用的钩子方法，请参见下面，
     * 这些方法允许LinkedHashMap内部保持独立于这些机制。
     * (这还要求将map实例传递给一些可能创建新节点的实用程序方法。)
     *
     * 基于并行编程的、类似于ssa的编码风格有助于消除所有扭曲指针中的错误.
     */

    /**
     * 默认的初始容量，1 << 4,16，必须是2的幂
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    /**
     * 最大的容量，1 << 30,如果构造函数指定了一个更高的值时，使用。
     * 容量一定是2的幂，而且 <=  1<<30
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * 如果构造器中，没有指定负载因子，负载因子的值，0.75
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /**
     * 桶的数量界限，桶使用树而不是列表。
     * 当加入一个元素到一个至少有这么多节点的桶时，桶被转换为树。
     * 这个值必须必2大，并且应该至少是8，以便桶收缩为普通桶时，树的移除的假定相合。
     * 加入这个节点到桶前，有8个，加入后，有9个节点，则树化桶
     */
    static final int TREEIFY_THRESHOLD = 8;

    /**
     * 桶的数量限制，在resize操作中，反树化桶。
     * 应该小于TREEIFY_THRESHOLD，至少为6，来与删除时，的收缩探测相合。
     * resize操作时，新的桶的节点数<=6,对桶反树化
     */
    static final int UNTREEIFY_THRESHOLD = 6;

    /**
     * 桶可以被树化的，最小的哈希表的容量。
     * （否则如果一个桶中有太多的节点时，表被resize）
     * 应该至少是4 * TREEIFY_THRESHOLD，来避免resize和树化之间的冲突。
     * 如果树化桶时，表的长度 < MIN_TREEIFY_CAPACITY=64，则进行resize操作，而不进行树化桶
     */
    static final int MIN_TREEIFY_CAPACITY = 64;

    /**
     * 普通的哈希桶节点，给大部分entry使用。
     * （看下面TreeNode的子类和LinkedHashMap的Entry子类）
     * 节点与节点的关系，类似于linkedlist的Node，但是节点与节点之间是单向链表，不是双向的
     */
    static class Node<K,V> implements Map.Entry<K,V> {
    	// hash是 key.hashcode ^ (hashcode >>> 16) 即高位16位不变，低位16位与高位16位进行亦或运算。	
        final int hash; // hash是final的，根据构造函数传入
        final K key; // key是final的，根据构造函数传入
        V value; // value不是final，可以用setvalue改变
        Node<K,V> next; // 有next的下一个节点，由此可见是类似于linkedlist的。
        // 但是只有next，没有prev，是单向的

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                //key与value都相同，节点相同
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

    /* ---------------- Static utilities -------------- */

    /**
     * 计算key.hashCode()，并且将高位的hash传递到低位（通过亦或XOR）。
     * 因为哈希表使用2的幂作为掩码，所以仅仅在当前掩码之上的位发生变动的hashcode，会永远冲突。（就是低位不变，高位变）
     * （已知的例子是float作为key，小表中保存连续的数字）
     * 所以，我们做一个转换，将高位bit的影响扩展到低位。
     * 这是在时间，空间和位的扩展质量之间的权衡。
     * 因为许多普通的hashcode的集合是合理地分布的。（所以不因为扩展而受益），
     * 并且因为我们使用树来处理桶中的巨量冲突，我们仅仅使用XOR改变位，以最便宜的可行方式来减少性能的亏损，
     * 同时包含了高位的影响，高位因为哈希表大小的限制，从来不会被用于计算之内。
     */
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
        // null 为 0
        // 否则结果为 hashcode ^ (hashcode >>> 16) 即高位16位不变，低位16位与高位16位进行亦或运算。
    }

    /**
     * 返回x的类，如果它的类C是实现了Comparable < C > 接口的，否则返回null
     */
    static Class<?> comparableClassFor(Object x) {
        if (x instanceof Comparable) {
            Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
            if ((c = x.getClass()) == String.class) // bypass checks
            	//如果运行时类型是String，直接返回
                return c;
            if ((ts = c.getGenericInterfaces()) != null) {
            	// ts为这个类直接实现的接口，对ts进行遍历
                for (int i = 0; i < ts.length; ++i) {
                    if (((t = ts[i]) instanceof ParameterizedType) &&
                        ((p = (ParameterizedType)t).getRawType() ==
                         Comparable.class) &&
                        (as = p.getActualTypeArguments()) != null &&
                        as.length == 1 && as[0] == c) // type arg is c
                    	//如果接口是Comparable，返回类c
                        return c;
                }
            }
        }
        //x不是Comparable接口的，直接返回null
        return null;
    }

    /**
     * 如果x匹配kc（k是筛选过的Comparable的类），返回k.compareTo(x)，否则返回0.
     */
    @SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable
    static int compareComparables(Class<?> kc, Object k, Object x) {
    	// 如果x为null，或者x的类不是kc，返回0
        return (x == null || x.getClass() != kc ? 0 :
                ((Comparable)k).compareTo(x)); // 否则返回k.compareTo(x)
    }

    /**
     * 对于给定的目标容量，返回一个2的幂。（例如cap=32或者30，返回32）
     * <p>这个方法给public HashMap(int initialCapacity, float loadFactor) 用.
     * <p>如果用户输入一个不为2的幂的数字，将它调整为一个是2的幂的数字，刚刚 > = cap
     */
    static final int tableSizeFor(int cap) {
        int n = cap - 1; // 如果cap已经是2的幂， 又没有执行这个减1操作，则执行完后面的几条无符号右移操作之后，返回的capacity将是这个cap的2倍。
        n |= n >>> 1; // 最高位为1，1xx | 01x = 11x 最高位的后一位变为1，包括最高位2位为1
        n |= n >>> 2; // 11xxx | 0011x = 1111x  包括最高位4位为1
        n |= n >>> 4; // 包括最高位8位为1
        n |= n >>> 8; // 包括最高位16位为1
        n |= n >>> 16; // 包括最高位32位为1
        // 到这里保证n的最高位后面的所有位为1
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
        // 最后n<0 ,返回1
        // n=0，返回1
        // n>0，返回n+1 111111 + 1 =100000 最后返回2的幂
    }

    /* ---------------- Fields -------------- */

    /**
     * 哈希表，第一次使用时，初始化，根据需要调整大小。
     * 当分配空间时，长度永远是2的幂。
     * （在一些操作中，我们长度为0，来允许当前不需要的引导机制。
     * 注意：HashMap.TreeNode<K,V> extends LinkedHashMap.Entry<K,V>
     * LinkedHashMap.Entry<K,V> extends HashMap.Node<K,V>
     * 所以TreeNode是Node的子类
     */
    transient Node<K,V>[] table;

    /**
     * 保存着缓存的entrySet().
     * 注意：AbstractMap的字段为了keySet() 和 values() 使用。
     * （AbstractMap有keySet和values字段，Hashmap有entrySet字段。）
     */
    transient Set<Map.Entry<K,V>> entrySet;

    /**
     * map中key-value映射的数量。
     */
    transient int size;

    /**
     * 这个Hashmap在结构上被改变的次数。
     * 结构上的改变是那些改变Hashmap中映射的数量，或者一个改变内部结构的方式（例如调整大小，rehash）
     * 这个字段让HashMap的集合视图上的迭代器快速失败。
     */
    transient int modCount;

    /**
     * 下一次调整大小时的size的值。(capacity * load factor).
     *
     * @serial
     */
    // (序列化时javadoc描述为true。此外，如果没有分配表数组，则此字段保留初始数组容量，或零表示
    int threshold;

    /**
     * 哈希表的负载因子。
     * <p>capacity * load factor= size
     * <p>size/load factor=capacity
     * <p>size/capacity=load factor
     * @serial
     */
    final float loadFactor;

    /* ---------------- Public operations -------------- */

    /**
     * 创建一个有着指定初始容量和负载因子的空的HashMap
     *
     * @param  initialCapacity the initial capacity
     * @param  loadFactor      the load factor
     * @throws IllegalArgumentException if the initial capacity is negative
     *         or the load factor is nonpositive
     */
    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        //loadFactor>0,直接设置给loadFactor
        this.loadFactor = loadFactor;
        //  0<=initialCapacity<=MAXIMUM_CAPACITY=1<<30
        // 设置initialCapacity的一个2的幂（即大于等于initialCapacity的2的幂）
        // 再赋值给threshold，不初始化table!!!
        this.threshold = tableSizeFor(initialCapacity);
    }

    /**
     * 创建一个有着指定初始容量和默认负载因子（0.75）的空的HashMap
     *
     * @param  initialCapacity the initial capacity.
     * @throws IllegalArgumentException if the initial capacity is negative.
     */
    public HashMap(int initialCapacity) {
    	//使用上面的构造函数，loadFactor=DEFAULT_LOAD_FACTOR=0.75
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    /**
     * 创建一个有着默认初始容量（16）和默认负载因子（0.75）的空的HashMap
     */
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
        // 只设置loadFactor，不设置threshold，threshold还是为0
    }

    /**
     * 创建一个与指定map相同映射的新的HashMap。
     * 这个HashMap创建，有默认的负载因子（0.75），有一个足够容纳指定map的映射的初始容量。
     *
     * @param   m the map whose mappings are to be placed in this map
     * @throws  NullPointerException if the specified map is null
     */
    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        // 设置loadFactor，然后全部插入m的映射
        putMapEntries(m, false);
    }

    /**
     * 实现Map.putAll方法和Map的构造器
     *
     * @param m the map
     * @param evict false when initially constructing this map, else
     * true (relayed to method afterNodeInsertion).
     */
    final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
        int s = m.size();
        if (s > 0) {
            if (table == null) { // pre-size
            	//此时，map为空
            	// ft为map放入指定map需要的threshold
                float ft = ((float)s / loadFactor) + 1.0F;
                // t为ft与MAXIMUM_CAPACITY的较小的数
                int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                         (int)ft : MAXIMUM_CAPACITY);
                if (t > threshold)
                	// 设置threshold为大于等于t的2的幂
                    threshold = tableSizeFor(t);
            }
            else if (s > threshold)
                resize();
            for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
                K key = e.getKey();
                V value = e.getValue();
                // 逐个调用putVal方法进入，注意：参数为false和evict
                putVal(hash(key), key, value, false, evict);
            }
        }
    }

    /**
     * 返回map中key-value对的数量。
     *
     * @return the number of key-value mappings in this map
     */
    public int size() {
        return size;
    }

    /**
     * 如果map不包含任何key-value对，返回true
     *
     * @return <tt>true</tt> if this map contains no key-value mappings
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 得到指定key映射的value，或者如果map不包含key对于的映射，返回null
     *
     * <p>更正式地，如果map包含一个这样的映射，里面的key k 和value v是这样的
     * {@code (key==null ? k==null :key.equals(k))} ，那么方法返回v。
     * 否则，返回null。（里面最多一个这样的映射）
     *
     * <p>返回null，不一定表明map不包含这个key对应的映射。
     * 也可能key对应的值为null。
     * containsKey操作可以用于辨明这两种情况。
     *
     * @see #put(Object, Object)
     */
    public V get(Object key) {
        Node<K,V> e;
        // 根据getNode方法得到节点e，再返回e的value
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

    /**
     * 实现Map.get并且关联方法。
     *
     * @param hash hash for key
     * @param key the key
     * @return the node, or null if none
     */
    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        // 把table赋值给tab，table的长度赋值给n
        if ((tab = table) != null && (n = tab.length) > 0 &&
        	// first是哈希表中key对应节点所处在的那个桶的头一个节点。
        	// 那个桶的index为 table.length-1 & hash （即获取hash的低位的x位,table.length = 2 ^ x）
        	// hash是 key.hashcode ^ (hashcode >>> 16) 即高位16位不变，低位16位与高位16位进行亦或运算。	
            (first = tab[(n - 1) & hash]) != null) {
        	// 先检查first.hash与hash是否相同
            if (first.hash == hash && // 永远检查first节点
            	// 将first.key赋值给k，并检查k与key是否是同一个引用，或者equals相同
                ((k = first.key) == key || (key != null && key.equals(k))))
            	// 两个都相同，返回first
                return first;
            // 到这里说明first不为对应节点，如果first.next不为null，则检查first后面的节点
            // 将first.next赋值给e
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                	// 如果first是TreeNode，则返回TreeNode的getTreeNode方法
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                	// 这里，说明first是普通节点
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                    	// 检查e的hash与e的key是否对应
                        return e;
                  // 根据链表 e = e.next 不断检查，直到next为null  
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

    /**
     * 如果map包含有着指定的key的映射，返回true。
     *
     * @param   key   The key whose presence in this map is to be tested
     * @return <tt>true</tt> if this map contains a mapping for the specified
     * key.
     */
    public boolean containsKey(Object key) {
    	// 得到节点的节点，根据是否为null，判断是否有这个key
    	// get是返回node的value，所以有可能返回null
        return getNode(hash(key), key) != null;
    }

    /**
     * 将指定的key与指定的value在这个map中关联（可选操作）。
     * 如果map之前包含了这个key的映射，旧的value被指定value替代。
     *
     * @param key key with which the specified value is to be associated
     * @param value value to be associated with the specified key
     * @return the previous value associated with <tt>key</tt>, or
     *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
     *         (A <tt>null</tt> return can also indicate that the map
     *         previously associated <tt>null</tt> with <tt>key</tt>.)
     */
    public V put(K key, V value) {
    	// 调用putVal方法
        return putVal(hash(key), key, value, false, true);
    }

    /**
     * 实现Map.put并且关联方法。
     *
     * @param hash hash for key
     * @param key the key
     * @param value the value to put
     * @param onlyIfAbsent 如果true，则不改变已经存在的value
     * @param evict 如果false，哈希表处于创建阶段。
     * @return previous value, or null if none
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        // 把table赋值给tab，table的长度赋值给n
        if ((tab = table) == null || (n = tab.length) == 0)
        	// 如果tab为null或者长度为0，则调用resize方法
        	// 返回初始化后的节点数组，赋值给tab，同时table的长度赋值给n
            n = (tab = resize()).length;
        // 把哈希表中对应的桶赋值给p
        if ((p = tab[i = (n - 1) & hash]) == null)
        	//如果hash对应的桶为null，则新建一个节点，赋值给那个桶
            tab[i] = newNode(hash, key, value, null);
        else {
        	// 如果对应的桶不为null
            Node<K,V> e; K k;
            // 下面的代码目的是找到在p这个桶下，hash和key对应的已经存在的那个节点，赋值给e
            if (p.hash == hash &&
            	// 把p的key赋值给k
                ((k = p.key) == key || (key != null && key.equals(k))))
            	// 如果p的hash和key正确，将p赋给e
                e = p;
            else if (p instanceof TreeNode)
            	// 如果p是TreeNode，调用putTreeVal方法，将返回值赋给e
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                	// 将p.next赋给e
                	// 如果e为null，说明链表到头，构造新节点，hash，key，value，然后设置给p.next，然后跳出
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        	// binCount为原来的数目-1，binCount+1为原来的数目
                        	// 如果binCount+1>=TREEIFY_THRESHOLD=8
                        	// 原来的数目>=8，加入后，有9个节点，则树化桶
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                    	// 如果e的数据正确，跳出
                        break;
                    // 将e赋给p，就是p=p.next
                    p = e;
                }
            }
            if (e != null) { // 这种情况不是新增节点，而是对已经存在节点进行修改
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

    /**
     * 初始化或者倍化表的大小（*2）。
     * 如果表为null，使用字段threshold作为初始容量目标，分配空间。
     * 否则，因为我们使用2的幂的扩展，每个桶的元素，要么待在同一个index的桶，要么index+新表中2的幂。
     * 比如110+1000=1110，就是加了2的幂
     *
     * @return the table
     */
    final Node<K,V>[] resize() {
    	// 将现在的table赋值给oldTab
        Node<K,V>[] oldTab = table;
        // 如果现在的table，oldCap=0，否则为table.length
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        // 将threshold赋值给oldThr
        int oldThr = threshold;
        int newCap, newThr = 0;
        // 下面的代码是得到新的容量和阀值，即newCap, newThr
        if (oldCap > 0) {
        	// 如果oldCap>0,说明是扩容（*2）的情况
            if (oldCap >= MAXIMUM_CAPACITY) {
            	// 如果oldCap超过限制，则设置threshold = Integer.MAX_VALUE，将现在的table直接返回
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            // 将oldCap << 1 赋值给newCap
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
            	// 如果nexCap<MAXIMUM_CAPACITY , oldCap >=16，
            	// 将oldThr << 1 赋值给newThr
                newThr = oldThr << 1; // double threshold
        }
        // 到这里说明是哈希表新建的情况
        else if (oldThr > 0) // threshold字段保存了初始容量（如果设置了）
        	// 将oldThr 赋值给newCap
            newCap = oldThr;
        else {               // 没有指定初始容量，即threshold为0，则容量为默认值。
        	// 将16赋值给newCap
        	// 将12赋值给newThr
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }       
        if (newThr == 0) {
        	// 这里说明要么新建哈希表指定了初始容量，要么nexCap>MAXIMUM_CAPACITY , oldCap < 16
        	// 根据newCap和loadFactor重新设置threshold
            float ft = (float)newCap * loadFactor;
            // 如果nexCap>MAXIMUM_CAPACITY，则newThr=Integer.MAX_VALUE
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        // 将newThr赋值给threshold
        // 将new Node[newCap]赋值给newTab
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        // 将newTab赋值给table
        table = newTab;
        if (oldTab != null) {
        	// 如果oldTab != null，则是扩容状态，对旧表的数据向新表迁移
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                // 对oldTab进行遍历，将oldTab[j]赋值给e
                if ((e = oldTab[j]) != null) {
                	// 如果e不为null，则迁移
                	// 将旧表清空，oldTab[j] = null
                    oldTab[j] = null;
                    if (e.next == null)
                    	// 如果只有一个节点，新的index为  e.hash & (newCap - 1)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                    	// 如果e是TreeNode，调用e的split方法进行重新分配
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // 保持顺序
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                        	// 将e.next赋值给next
                            next = e.next;
                            // oldCap=1000，newCap=10000
                            // 本来要放入新桶的hash & (newCap-1) = hash & 1111
                            // 现在hash & oldCap = hash & 1000
                            // 如果结果为0，hash为0xxx，说明 hash & 1111=hash & 0111，还是在原来的桶
                            // 如果结果不为0，hash为1xxx，
                            
                            if ((e.hash & oldCap) == 0) {
                            	//(e.hash & oldCap) == 0，说明还是在原来的桶
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                                // 在lo中，形成一个链表，第一个为head，接下来不断放在tail的next
                                // newTab[j] = loHead;
                            }
                            else {
                            	// 说明在另一个桶
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                             // 在hi中，形成一个链表，第一个为head，接下来不断放在tail的next
                             // newTab[j + oldCap] = hiHead;   
                            }
                        } while ((e = next) != null);
                        //设置完两个链表后，将两个head赋值给新表中两个桶
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

    /**
     * 将哈希表中根据给定hash得到的index里的桶里的全部节点替换，
     * 如果表太小，不提货，进行resize
     */
    final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        // 将tab.length赋值给n
        // 如果tab为null或者tab.length < MIN_TREEIFY_CAPACITY=64，进行resize操作，不进行树化桶
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
        // 将(n - 1) & hash赋值给index
        // 将tab中index的桶赋给e
        // 如果e不为null，进行树化
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            TreeNode<K,V> hd = null, tl = null;
            do {
            	// return new TreeNode<>(p.hash, p.key, p.value, next);
            	// 将一个有着e的hash，key，value，next为null的TreeNode赋值给p，
                TreeNode<K,V> p = replacementTreeNode(e, null);
                if (tl == null)
                	// 如果尾节点tl为null，将p赋值给root节点hd
                    hd = p;
                else {
                	// 否则，设置p的prev，设置tl的next
                    p.prev = tl;
                    tl.next = p;
                }
                // 将p赋值给尾节点tl
                tl = p;
                // 不断e=e.next
            } while ((e = e.next) != null);
            // 将root节点hd赋值给tab[index]
            if ((tab[index] = hd) != null)
            	//转换为TreeNode节点后，进行树化
                hd.treeify(tab);
        }
    }

    /**
     * 复制指定map，所有的映射，到这个map。
     * 这个map和指定map都有的key，对应的映射会被替换。
     * 
     *
     * @param m mappings to be stored in this map
     * @throws NullPointerException if the specified map is null
     */
    public void putAll(Map<? extends K, ? extends V> m) {
        putMapEntries(m, true);
    }

    /**
     * 将map中key对应的映射移除，如果映射存在
     *
     * @param  key key whose mapping is to be removed from the map
     * @return the previous value associated with <tt>key</tt>, or
     *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
     *         (A <tt>null</tt> return can also indicate that the map
     *         previously associated <tt>null</tt> with <tt>key</tt>.)
     */
    public V remove(Object key) {
        Node<K,V> e;
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
    }

    /**
     * 实现remove和相关的方法
     *
     * @param hash hash for key
     * @param key the key
     * @param value the value to match if matchValue, else ignored
     * @param matchValue if true only remove if value is equal
     * @param movable if false do not move other nodes while removing
     * @return the node, or null if none
     */
    final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
        Node<K,V>[] tab; Node<K,V> p; int n, index;
        // 将table赋值给tab，tab.length赋值给n
        //(n - 1) & hash赋值给index ， tab[index]赋值给p
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (p = tab[index = (n - 1) & hash]) != null) {
            Node<K,V> node = null, e; K k; V v;
            // 将p的key赋值给k
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
            	// 如果p的hash和key对应，将p赋值给node
                node = p;
            // 不对应的话，将p.next赋值给e，如果e不为null
            else if ((e = p.next) != null) {
                if (p instanceof TreeNode)
                	// 如果p是TreeNode，将p.getTreeNode(hash, key)赋值给node
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                else {
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) {
                        	// 如果e不为null，p也不是TreeNode，不断遍历链表，找到对应的节点e，赋值给node
                            node = e;
                            break;
                        }
                        p = e;
                    } while ((e = e.next) != null);
                }
            }
            if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) {
            	// 如果node不为null，并根据matchValue与node的value的对应关系
                if (node instanceof TreeNode)
                	// 如果node是TreeNode，调用node的removeTreeNode(this, tab, movable)
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                else if (node == p)
                	// 如果node是p，即node是头结点，tab[index] = node.next
                    tab[index] = node.next;
                else
                	// 否则p为node的上一个节点，p.next = node.next
                    p.next = node.next;
                ++modCount;
                --size;
                // 调用afterNodeRemoval(node)
                afterNodeRemoval(node);
                return node;
            }
        }
        return null;
    }

    /**
     * 删除map中所有的映射。
     * 调用返回后，map为空。
     */
    public void clear() {
        Node<K,V>[] tab;
        modCount++;
        if ((tab = table) != null && size > 0) {
        	// size设为0，tab的每个桶都设为null
            size = 0;
            for (int i = 0; i < tab.length; ++i)
                tab[i] = null;
        }
    }

    /**
     * 如果map包含有着一个或多个指定的value的映射，返回true。
     *
     * @param value value whose presence in this map is to be tested
     * @return <tt>true</tt> if this map maps one or more keys to the
     *         specified value
     */
    public boolean containsValue(Object value) {
        Node<K,V>[] tab; V v;
        if ((tab = table) != null && size > 0) {
        	// 对tab进行循环
            for (int i = 0; i < tab.length; ++i) {
            	// 对tab[i]不断next进行迭代
                for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                    if ((v = e.value) == value ||
                        (value != null && value.equals(v)))
                    	// 找到value对应的，返回true
                        return true;
                }
            }
        }
        return false;
    }

    /**
     * 返回这个map中包含的key的set视图。
     * set由map支持，所以对map的改变会反映到set中，反之亦然。
     * 如果map被修改，同时set的迭代正在进行（除了通过Iterator自己的remove操作），迭代的结果未知。
     * set支持元素的删除，会导致map中对应的映射被删除，通过Iterator.remove，Set.remove，
     * removeAll，retainAll，clear操作。
     * set不支持add或者addAll操作。
     *
     * @return a set view of the keys contained in this map
     */
    public Set<K> keySet() {
    	// 单例模式，没有则创建一个keySet，一个hashMap一个keySet
        Set<K> ks = keySet;
        if (ks == null) {
            ks = new KeySet();
            keySet = ks;
        }
        return ks;
    }

    final class KeySet extends AbstractSet<K> {
    	// size，clear，contains，remove，分别调用hashmap的size，clear，containsKey，removeNode方法
        public final int size()                 { return size; }
        public final void clear()               { HashMap.this.clear(); }
        // 迭代器返回KeyIterator
        public final Iterator<K> iterator()     { return new KeyIterator(); }
        public final boolean contains(Object o) { return containsKey(o); }
        public final boolean remove(Object key) {
            return removeNode(hash(key), key, null, false, true) != null;
        }
        // 分割器返回KeySpliterator
        public final Spliterator<K> spliterator() {
            return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);
        }
        public final void forEach(Consumer<? super K> action) {
            Node<K,V>[] tab;
            if (action == null)
                throw new NullPointerException();
            if (size > 0 && (tab = table) != null) {
                int mc = modCount;
                // 对HashMap的表tab，的每个桶，不断e=e.next，进行遍历
                for (int i = 0; i < tab.length; ++i) {
                    for (Node<K,V> e = tab[i]; e != null; e = e.next)
                        action.accept(e.key);
                }
                if (modCount != mc)
                    throw new ConcurrentModificationException();
            }
        }
    }

    /**
     * 返回这个map中包含的value的collection视图。
     * collection由map支持，所以对map的改变会反映到collection中，反之亦然。
     * 如果map被修改，同时collection的迭代正在进行（除了通过Iterator自己的remove操作），迭代的结果未知。
     * collection支持元素的删除，会导致map中对应的映射被删除，通过Iterator.remove，collection.remove，
     * removeAll，retainAll，clear操作。
     * collection不支持add或者addAll操作。
     *
     * @return a view of the values contained in this map
     */
    public Collection<V> values() {
        Collection<V> vs = values;
        if (vs == null) {
            vs = new Values();
            values = vs;
        }
        return vs;
    }
    
    // 如同keySet
    final class Values extends AbstractCollection<V> {
        public final int size()                 { return size; }
        public final void clear()               { HashMap.this.clear(); }
        public final Iterator<V> iterator()     { return new ValueIterator(); }
        public final boolean contains(Object o) { return containsValue(o); }
        public final Spliterator<V> spliterator() {
            return new ValueSpliterator<>(HashMap.this, 0, -1, 0, 0);
        }
        public final void forEach(Consumer<? super V> action) {
            Node<K,V>[] tab;
            if (action == null)
                throw new NullPointerException();
            if (size > 0 && (tab = table) != null) {
                int mc = modCount;
                for (int i = 0; i < tab.length; ++i) {
                    for (Node<K,V> e = tab[i]; e != null; e = e.next)
                        action.accept(e.value);
                }
                if (modCount != mc)
                    throw new ConcurrentModificationException();
            }
        }
    }

    /**
     * 返回这个map中包含的映射的set视图。
     * set由map支持，所以对map的改变会反映到set中，反之亦然。
     * 如果map被修改，同时set的迭代正在进行（除了通过Iterator自己的remove操作），迭代的结果未知。
     * set支持元素的删除，会导致map中对应的映射被删除，通过Iterator.remove，Set.remove，
     * removeAll，retainAll，clear操作。
     * set不支持add或者addAll操作。
     *
     * @return a set view of the mappings contained in this map
     */
    public Set<Map.Entry<K,V>> entrySet() {
        Set<Map.Entry<K,V>> es;
        return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
    }

    final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
        public final int size()                 { return size; }
        public final void clear()               { HashMap.this.clear(); }
        public final Iterator<Map.Entry<K,V>> iterator() {
            return new EntryIterator();
        }
        public final boolean contains(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry<?,?> e = (Map.Entry<?,?>) o;
            Object key = e.getKey();
            // 先根据key，getNode方法得到Node，再判断value是否相同
            Node<K,V> candidate = getNode(hash(key), key);
            return candidate != null && candidate.equals(e);
        }
        public final boolean remove(Object o) {
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>) o;
                Object key = e.getKey();
                Object value = e.getValue();
                // 删除key和value都对应的节点
                return removeNode(hash(key), key, value, true, true) != null;
            }
            return false;
        }
        public final Spliterator<Map.Entry<K,V>> spliterator() {
            return new EntrySpliterator<>(HashMap.this, 0, -1, 0, 0);
        }
        public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
            Node<K,V>[] tab;
            if (action == null)
                throw new NullPointerException();
            if (size > 0 && (tab = table) != null) {
                int mc = modCount;
                for (int i = 0; i < tab.length; ++i) {
                    for (Node<K,V> e = tab[i]; e != null; e = e.next)
                        action.accept(e);
                }
                if (modCount != mc)
                    throw new ConcurrentModificationException();
            }
        }
    }

    // 覆盖了JDK8的Map，附加的方法（原来都是default的）

    @Override
    public V getOrDefault(Object key, V defaultValue) {
        Node<K,V> e;
        // getNode赋值给e，返回null时，返回defaultValue，否则返回e.value
        return (e = getNode(hash(key), key)) == null ? defaultValue : e.value;
    }

    @Override
    public V putIfAbsent(K key, V value) {
    	// put时是  return putVal(hash(key), key, value, false, true);
    	// 第三个参数  onlyIfAbsent 如果true，则不改变已经存在的value
        return putVal(hash(key), key, value, true, true);
    }

    @Override
    public boolean remove(Object key, Object value) {
    	// remove(key) 方法是   removeNode(hash(key), key, null, false, true))
    	// 第三个参数 value the value to match if matchValue, else ignored
        // 第四个参数 matchValue if true only remove if value is equal
        return removeNode(hash(key), key, value, true, true) != null;
    }

    @Override
    public boolean replace(K key, V oldValue, V newValue) {
        Node<K,V> e; V v;
        if ((e = getNode(hash(key), key)) != null &&
            ((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {
        	// 如果getNode的结果赋值给e，e不为null，并且e的value与oldValue相同
        	// newValue赋值给e.value
            e.value = newValue;
            afterNodeAccess(e);
            return true;
        }
        return false;
    }

    @Override
    public V replace(K key, V value) {
        Node<K,V> e;
        if ((e = getNode(hash(key), key)) != null) {
        	// 如上，不判断oldValue
            V oldValue = e.value;
            e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
        return null;
    }

    @Override
    public V computeIfAbsent(K key,
                             Function<? super K, ? extends V> mappingFunction) {
        if (mappingFunction == null)
            throw new NullPointerException();
        int hash = hash(key);
        Node<K,V>[] tab; Node<K,V> first; int n, i;
        int binCount = 0;
        TreeNode<K,V> t = null;
        Node<K,V> old = null;
        if (size > threshold || (tab = table) == null ||
            (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 先得到hash对应的桶，然后类似于getNode，得到key对应的那个节点，赋值给old，
        if ((first = tab[i = (n - 1) & hash]) != null) {
            if (first instanceof TreeNode)
            	// 如果first是TreeNode，将key对应的节点赋值给t，也赋值给old
                old = (t = (TreeNode<K,V>)first).getTreeNode(hash, key);
            else {
                Node<K,V> e = first; K k;
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k)))) {
                        old = e;
                        break;
                    }
                    ++binCount;
                } while ((e = e.next) != null);
            }
            V oldValue;
            // 如果old和oldValue不为null，直接返回
            if (old != null && (oldValue = old.value) != null) {
                afterNodeAccess(old);
                return oldValue;
            }
        }
        // 使用给出的function算出v
        V v = mappingFunction.apply(key);
        // 如果为null，直接返回null
        if (v == null) {
            return null;
            // 如果old不为null，即old对应的key存在，但是value原来是null，设置节点value为v
        } else if (old != null) {
            old.value = v;
            afterNodeAccess(old);
            return v;
        }
        else if (t != null)
        	// 此时桶为树桶，调用t的putTreeVal
            t.putTreeVal(this, tab, hash, key, v);
        else {
        	// 普通的桶，在桶处新建一个，然后新节点的next为原来的first
            tab[i] = newNode(hash, key, v, first);
            if (binCount >= TREEIFY_THRESHOLD - 1)
                treeifyBin(tab, hash);
        }
        ++modCount;
        ++size;
        afterNodeInsertion(true);
        return v;
    }

    public V computeIfPresent(K key,
                              BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
        if (remappingFunction == null)
            throw new NullPointerException();
        Node<K,V> e; V oldValue;
        int hash = hash(key);
        // 先getNode，然后如果key对应的value存在，而且非null
        if ((e = getNode(hash, key)) != null &&
            (oldValue = e.value) != null) {
        	// 计算出v，如果v不为null，设置e的value
            V v = remappingFunction.apply(key, oldValue);
            if (v != null) {
                e.value = v;
                afterNodeAccess(e);
                return v;
            }
            else
            	// 如果function返回null，映射被删除
                removeNode(hash, key, null, false, true);
        }
        return null;
    }

    @Override
    public V compute(K key,
                     BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
        if (remappingFunction == null)
            throw new NullPointerException();
        int hash = hash(key);
        Node<K,V>[] tab; Node<K,V> first; int n, i;
        int binCount = 0;
        TreeNode<K,V> t = null;
        Node<K,V> old = null;
        if (size > threshold || (tab = table) == null ||
            (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((first = tab[i = (n - 1) & hash]) != null) {
            if (first instanceof TreeNode)
                old = (t = (TreeNode<K,V>)first).getTreeNode(hash, key);
            else {
                Node<K,V> e = first; K k;
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k)))) {
                        old = e;
                        break;
                    }
                    ++binCount;
                } while ((e = e.next) != null);
            }
        }
        // 先根据key得到对应的old，再设置oldValue
        V oldValue = (old == null) ? null : old.value;
        // 根据key和oldValue计算出v
        V v = remappingFunction.apply(key, oldValue);
        if (old != null) {
            if (v != null) {
            	// 如果function返回不为null，重新设置old的value。
                old.value = v;
                afterNodeAccess(old);
            }
            else
            	// 如果function返回null，移除这个映射（如果一开始就没有，就还是没有）。
                removeNode(hash, key, null, false, true);
        }
        // 如果没有原来节点，加入key，v键值对
        else if (v != null) {
            if (t != null)
                t.putTreeVal(this, tab, hash, key, v);
            else {
                tab[i] = newNode(hash, key, v, first);
                if (binCount >= TREEIFY_THRESHOLD - 1)
                    treeifyBin(tab, hash);
            }
            ++modCount;
            ++size;
            afterNodeInsertion(true);
        }
        return v;
    }

    @Override
    public V merge(K key, V value,
                   BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
        if (value == null)
            throw new NullPointerException();
        if (remappingFunction == null)
            throw new NullPointerException();
        int hash = hash(key);
        Node<K,V>[] tab; Node<K,V> first; int n, i;
        int binCount = 0;
        TreeNode<K,V> t = null;
        Node<K,V> old = null;
        if (size > threshold || (tab = table) == null ||
            (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((first = tab[i = (n - 1) & hash]) != null) {
            if (first instanceof TreeNode)
                old = (t = (TreeNode<K,V>)first).getTreeNode(hash, key);
            else {
                Node<K,V> e = first; K k;
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k)))) {
                        old = e;
                        break;
                    }
                    ++binCount;
                } while ((e = e.next) != null);
            }
        }
        if (old != null) {
            V v;
            if (old.value != null)
            	// 新的value为function根据oldValue和value得到的值
                v = remappingFunction.apply(old.value, value);
            else
                v = value;
            if (v != null) {
                old.value = v;
                afterNodeAccess(old);
            }
            else
                removeNode(hash, key, null, false, true);
            return v;
        }
        // 如果没有old，插入key，value的键值对
        if (value != null) {
            if (t != null)
                t.putTreeVal(this, tab, hash, key, value);
            else {
                tab[i] = newNode(hash, key, value, first);
                if (binCount >= TREEIFY_THRESHOLD - 1)
                    treeifyBin(tab, hash);
            }
            ++modCount;
            ++size;
            afterNodeInsertion(true);
        }
        return value;
    }

    @Override
    public void forEach(BiConsumer<? super K, ? super V> action) {
        Node<K,V>[] tab;
        if (action == null)
            throw new NullPointerException();
        if (size > 0 && (tab = table) != null) {
            int mc = modCount;
            for (int i = 0; i < tab.length; ++i) {
                for (Node<K,V> e = tab[i]; e != null; e = e.next)
                	// 对每个桶，每个桶内的节点，不断e = e.next，进行遍历
                    action.accept(e.key, e.value);
            }
            if (modCount != mc)
                throw new ConcurrentModificationException();
        }
    }

    @Override
    public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
        Node<K,V>[] tab;
        if (function == null)
            throw new NullPointerException();
        if (size > 0 && (tab = table) != null) {
            int mc = modCount;
            for (int i = 0; i < tab.length; ++i) {
                for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                	// value为function根据原来的key和value生成的新value
                    e.value = function.apply(e.key, e.value);
                }
            }
            if (modCount != mc)
                throw new ConcurrentModificationException();
        }
    }

    /* ------------------------------------------------------------ */
    // Cloning and serialization

    /**
     * 返回HashMap实例的浅复制：keys和values它们自己没有被复制。
     *
     * @return a shallow copy of this map
     */
    @SuppressWarnings("unchecked")
    @Override
    public Object clone() {
        HashMap<K,V> result;
        try {
            result = (HashMap<K,V>)super.clone();
        } catch (CloneNotSupportedException e) {
            // this shouldn't happen, since we are Cloneable
            throw new InternalError(e);
        }
        // 设置各个字段变成初始的默认值（null或者0）。
        result.reinitialize();
        // 把自己所有的entry加入result
        result.putMapEntries(this, false);
        return result;
    }

    // 下面两个方法在序列化HashSet时被使用
    final float loadFactor() { return loadFactor; }
    final int capacity() {
        return (table != null) ? table.length :
            (threshold > 0) ? threshold :
            DEFAULT_INITIAL_CAPACITY;
    }

    /**
     * 保存HashMap的状态为一个流，序列化
     *
     * @serialData The <i>capacity</i> of the HashMap (the length of the
     *             bucket array) is emitted (int), followed by the
     *             <i>size</i> (an int, the number of key-value
     *             mappings), followed by the key (Object) and value (Object)
     *             for each key-value mapping.  The key-value mappings are
     *             emitted in no particular order.
     */
    private void writeObject(java.io.ObjectOutputStream s)
        throws IOException {
        int buckets = capacity();
        // 写出threshold, loadfactor,和其他隐藏的元素
        s.defaultWriteObject();
        // 写桶的大小和size
        s.writeInt(buckets);
        s.writeInt(size);
        // 安装桶的顺序，桶内不断next的顺序，依次写入key和value
        internalWriteEntries(s);
    }

    /**
     * 从一个流，重组HashMap实例，反序列化
     */
    private void readObject(java.io.ObjectInputStream s)
        throws IOException, ClassNotFoundException {
        // 读入threshold, loadfactor,和其他隐藏的元素
        s.defaultReadObject();
        // 设置各个字段变成初始的默认值（null或者0）。
        reinitialize();
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new InvalidObjectException("Illegal load factor: " +
                                             loadFactor);
        s.readInt();                // 读入并忽略桶的数量
        int mappings = s.readInt(); // 读入映射的数量
        if (mappings < 0)
            throw new InvalidObjectException("Illegal mappings count: " +
                                             mappings);
        else if (mappings > 0) { // (如果mappings为0，使用默认的，即啥都不干)
        	// 计算table的大小，当给定的负载因子大小在0.25-4.0之间，使用它来计算
        	// lf为计算后的负载因子
            float lf = Math.min(Math.max(0.25f, loadFactor), 4.0f);
            // fc为映射数量和负载因子计算后的capacity
            float fc = (float)mappings / lf + 1.0f;
            // 根据capacity的上下限和tableSizeFor后的fc，得到cap，为table的大小
            int cap = ((fc < DEFAULT_INITIAL_CAPACITY) ?
                       DEFAULT_INITIAL_CAPACITY :
                       (fc >= MAXIMUM_CAPACITY) ?
                       MAXIMUM_CAPACITY :
                       tableSizeFor((int)fc));
            // 根据更新后的cap和lf计算出ft，然后根据上下限，和ft，计算出threshold
            float ft = (float)cap * lf;
            threshold = ((cap < MAXIMUM_CAPACITY && ft < MAXIMUM_CAPACITY) ?
                         (int)ft : Integer.MAX_VALUE);
            @SuppressWarnings({"rawtypes","unchecked"})
                Node<K,V>[] tab = (Node<K,V>[])new Node[cap];
            table = tab;

            // 读入key和value，将映射放入hashmap
            for (int i = 0; i < mappings; i++) {
                @SuppressWarnings("unchecked")
                    K key = (K) s.readObject();
                @SuppressWarnings("unchecked")
                    V value = (V) s.readObject();
                putVal(hash(key), key, value, false, false);
            }
        }
    }

    /* ------------------------------------------------------------ */
    // iterators

    abstract class HashIterator {
        Node<K,V> next;        // 下一个返回的entry
        Node<K,V> current;     // 当前的entry
        int expectedModCount;  // 为了快速失败机制
        int index;             // 下一个桶的index

        HashIterator() {
            expectedModCount = modCount; // 创建时记录modCount
            Node<K,V>[] t = table;
            current = next = null; // current和next为null
            index = 0; // index初始为0
            if (t != null && size > 0) { // 不断递进index，直到t[index]不为null，将t[index]赋值给next
            	// 循环完后，index是next对应桶的下一个桶的下标
                do {} while (index < t.length && (next = t[index++]) == null);
            }
        }

        public final boolean hasNext() {
            return next != null;
        }

        // KeyIterator等三个Iterator继承这个类，它们三个的next方法都调用这个方法，得到nextNode().key/value
        final Node<K,V> nextNode() {
            Node<K,V>[] t;
            Node<K,V> e = next; 
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            if (e == null)
                throw new NoSuchElementException();
            // 先将e赋值给current，再将current.next赋值给next
            // 如果next不为null，直接结束
            // next为null，并且t不为null，不断递进index，直到t[index]不为null，将t[index]赋值给next
            if ((next = (current = e).next) == null && (t = table) != null) {
                do {} while (index < t.length && (next = t[index++]) == null);
            }
            // 返回调用nextNode时的next
            return e;
        }

        public final void remove() {
            Node<K,V> p = current;
            if (p == null)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            // 设置current指针位null
            current = null;
            K key = p.key;
            // 删除key为current的key的节点
            removeNode(hash(key), key, null, false, false);
            expectedModCount = modCount;
        }
    }

    // 三者的hasNext，remove方法都相同
    // 只有next方法不一样，分别返回key，value，entry
    final class KeyIterator extends HashIterator
        implements Iterator<K> {
        public final K next() { return nextNode().key; }
    }

    final class ValueIterator extends HashIterator
        implements Iterator<V> {
        public final V next() { return nextNode().value; }
    }

    final class EntryIterator extends HashIterator
        implements Iterator<Map.Entry<K,V>> {
        public final Map.Entry<K,V> next() { return nextNode(); }
    }

    /* ------------------------------------------------------------ */
    // spliterators

    static class HashMapSpliterator<K,V> {
        final HashMap<K,V> map;
        Node<K,V> current;          // 当前节点，就是下一个处理的节点
        int index;                  // current index, modified on advance/split 当前index，在advance/split时修改
        int fence;                  // one past last index 最后一次的index
        int est;                    // size estimate 预计大小
        int expectedModCount;       // for comodification checks

        HashMapSpliterator(HashMap<K,V> m, int origin,
                           int fence, int est,
                           int expectedModCount) {
        	// return new EntrySpliterator<>(HashMap.this, 0, -1, 0, 0);
        	// super(m, origin, fence, est, expectedModCount);
            this.map = m; // map为自己
            this.index = origin; // 初始为0
            this.fence = fence; // 初始为-1
            this.est = est; // 初始为0
            this.expectedModCount = expectedModCount; // 初始为0
        }

        final int getFence() { // 第一次使用时，初始化fence和size
            int hi;
            // fence没有初始化前位-1
            // 将fence赋值给hi
            if ((hi = fence) < 0) {
            	// 如果hi小于0
                HashMap<K,V> m = map;
                // 设置est和modCount为map里的值
                est = m.size;
                expectedModCount = m.modCount;
                Node<K,V>[] tab = m.table;
                // fence设置为tab的length
                hi = fence = (tab == null) ? 0 : tab.length;
            }
            return hi;
        }

        public final long estimateSize() {
        	// 强制初始化，然后返回est，一开始为map的size
            getFence(); // force init
            return (long) est;
        }
    }

    static final class KeySpliterator<K,V>
        extends HashMapSpliterator<K,V>
        implements Spliterator<K> {
        KeySpliterator(HashMap<K,V> m, int origin, int fence, int est,
                       int expectedModCount) {
            super(m, origin, fence, est, expectedModCount);
        }

        public KeySpliterator<K,V> trySplit() {
        	// fence赋值给hi，index赋值给lo，mid为中间值        	
            int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
                // 如果lo>=mid（数目太少了）或者current不为null（指针在一个桶的中间，不能分割），时，返回null
                // 新的spliterator范围为[lo(index),mid)，大小为est/2
                // 自己的范围为[index(mid),fence)，大小为est/2
            return (lo >= mid || current != null) ? null :
                new KeySpliterator<>(map, lo, index = mid, est >>>= 1,
                                        expectedModCount);
        }

        public void forEachRemaining(Consumer<? super K> action) {
            int i, hi, mc;
            if (action == null)
                throw new NullPointerException();
            HashMap<K,V> m = map;
            Node<K,V>[] tab = m.table;
            // 如果没有初始化，进行初始化
            if ((hi = fence) < 0) {
                mc = expectedModCount = m.modCount;
                hi = fence = (tab == null) ? 0 : tab.length;
            }
            else
                mc = expectedModCount;
            if (tab != null && tab.length >= hi &&
                (i = index) >= 0 && (i < (index = hi) || current != null)) {
            	// 从current开始循环
                Node<K,V> p = current;
                current = null;
                do {
                	// 如果为null，到下一个桶
                	// 不为null，处理p的key，然后到p.next
                    if (p == null)
                        p = tab[i++];
                    else {
                        action.accept(p.key);
                        p = p.next;
                    }
                } while (p != null || i < hi); // 直到i为hi，即fence结束
                if (m.modCount != mc)
                    throw new ConcurrentModificationException();
            }
        }

        public boolean tryAdvance(Consumer<? super K> action) {
            int hi;
            if (action == null)
                throw new NullPointerException();
            Node<K,V>[] tab = map.table;
            // 如果tab.length<fence或者index<0，直接返回false
            if (tab != null && tab.length >= (hi = getFence()) && index >= 0) {
            	// 如果current不为null或者index<fence时，进入循环
                while (current != null || index < hi) {
                    if (current == null)
                    	// 如果current为null，current为tab[index]并且index递增
                        current = tab[index++];
                    else {
                        K k = current.key;
                        // current通过next进行递增，如果这个桶内，没有后续了，current之后为null
                        current = current.next;
                        // action接受current的key
                        action.accept(k);
                        if (map.modCount != expectedModCount)
                            throw new ConcurrentModificationException();
                        return true;
                    }
                }
            }
            return false;
        }

        public int characteristics() {
            return (fence < 0 || est == map.size ? Spliterator.SIZED : 0) |
                Spliterator.DISTINCT;
        }
    }

    static final class ValueSpliterator<K,V>
        extends HashMapSpliterator<K,V>
        implements Spliterator<V> {
        ValueSpliterator(HashMap<K,V> m, int origin, int fence, int est,
                         int expectedModCount) {
            super(m, origin, fence, est, expectedModCount);
        }

        public ValueSpliterator<K,V> trySplit() {
            int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
            return (lo >= mid || current != null) ? null :
                new ValueSpliterator<>(map, lo, index = mid, est >>>= 1,
                                          expectedModCount);
        }

        public void forEachRemaining(Consumer<? super V> action) {
            int i, hi, mc;
            if (action == null)
                throw new NullPointerException();
            HashMap<K,V> m = map;
            Node<K,V>[] tab = m.table;
            if ((hi = fence) < 0) {
                mc = expectedModCount = m.modCount;
                hi = fence = (tab == null) ? 0 : tab.length;
            }
            else
                mc = expectedModCount;
            if (tab != null && tab.length >= hi &&
                (i = index) >= 0 && (i < (index = hi) || current != null)) {
                Node<K,V> p = current;
                current = null;
                do {
                    if (p == null)
                        p = tab[i++];
                    else {
                        action.accept(p.value);
                        p = p.next;
                    }
                } while (p != null || i < hi);
                if (m.modCount != mc)
                    throw new ConcurrentModificationException();
            }
        }

        public boolean tryAdvance(Consumer<? super V> action) {
            int hi;
            if (action == null)
                throw new NullPointerException();
            Node<K,V>[] tab = map.table;
            if (tab != null && tab.length >= (hi = getFence()) && index >= 0) {
                while (current != null || index < hi) {
                    if (current == null)
                        current = tab[index++];
                    else {
                        V v = current.value;
                        current = current.next;
                        action.accept(v);
                        if (map.modCount != expectedModCount)
                            throw new ConcurrentModificationException();
                        return true;
                    }
                }
            }
            return false;
        }

        public int characteristics() {
            return (fence < 0 || est == map.size ? Spliterator.SIZED : 0);
        }
    }

    static final class EntrySpliterator<K,V>
        extends HashMapSpliterator<K,V>
        implements Spliterator<Map.Entry<K,V>> {
        EntrySpliterator(HashMap<K,V> m, int origin, int fence, int est,
                         int expectedModCount) {
            super(m, origin, fence, est, expectedModCount);
        }

        public EntrySpliterator<K,V> trySplit() {
            int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
            return (lo >= mid || current != null) ? null :
                new EntrySpliterator<>(map, lo, index = mid, est >>>= 1,
                                          expectedModCount);
        }

        public void forEachRemaining(Consumer<? super Map.Entry<K,V>> action) {
            int i, hi, mc;
            if (action == null)
                throw new NullPointerException();
            HashMap<K,V> m = map;
            Node<K,V>[] tab = m.table;
            if ((hi = fence) < 0) {
                mc = expectedModCount = m.modCount;
                hi = fence = (tab == null) ? 0 : tab.length;
            }
            else
                mc = expectedModCount;
            if (tab != null && tab.length >= hi &&
                (i = index) >= 0 && (i < (index = hi) || current != null)) {
                Node<K,V> p = current;
                current = null;
                do {
                    if (p == null)
                        p = tab[i++];
                    else {
                        action.accept(p);
                        p = p.next;
                    }
                } while (p != null || i < hi);
                if (m.modCount != mc)
                    throw new ConcurrentModificationException();
            }
        }

        public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
            int hi;
            if (action == null)
                throw new NullPointerException();
            Node<K,V>[] tab = map.table;
            if (tab != null && tab.length >= (hi = getFence()) && index >= 0) {
                while (current != null || index < hi) {
                    if (current == null)
                        current = tab[index++];
                    else {
                        Node<K,V> e = current;
                        current = current.next;
                        action.accept(e);
                        if (map.modCount != expectedModCount)
                            throw new ConcurrentModificationException();
                        return true;
                    }
                }
            }
            return false;
        }

        public int characteristics() {
            return (fence < 0 || est == map.size ? Spliterator.SIZED : 0) |
                Spliterator.DISTINCT;
        }
    }

    /* ------------------------------------------------------------ */
    // LinkedHashMap 支持


    /*
     * 下面的protected方法（包内的方法），被用来被LinkedHashMap覆盖，但不会被其他子类覆盖。
     * 几乎所有的其他内部方法也是protected的方法，但被声明是final的，能被LinkedHashMap，视图类，HashSet使用。
     */

    // 创建一个普通的节点（非树节点）
    Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
        return new Node<>(hash, key, value, next);
    }

    // 将TreeNode转换为普通节点
    Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
        return new Node<>(p.hash, p.key, p.value, next);
    }

    // 创建一个树节点
    TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
        return new TreeNode<>(hash, key, value, next);
    }

    // 将普通节点转为树节点
    TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
        return new TreeNode<>(p.hash, p.key, p.value, next);
    }

    /**
     * 设置各个字段变成初始的默认值（null或者0）。被clone和readObject方法调用。
     */
    void reinitialize() {
        table = null;
        entrySet = null;
        keySet = null;
        values = null;
        modCount = 0;
        threshold = 0;
        size = 0;
    }

    // 允许LinkedHashMap执行动作后的回调
    void afterNodeAccess(Node<K,V> p) { }
    void afterNodeInsertion(boolean evict) { }
    void afterNodeRemoval(Node<K,V> p) { }

    // 仅仅被writerObject调用，保证兼容的顺序。
    void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException {
        Node<K,V>[] tab;
        if (size > 0 && (tab = table) != null) {
            for (int i = 0; i < tab.length; ++i) {
                for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                	// 安装桶的顺序，桶内不断next的顺序，依次写入key和value
                    s.writeObject(e.key);
                    s.writeObject(e.value);
                }
            }
        }
    }

    /* ------------------------------------------------------------ */
    // 树桶

    /**
     * 对于树桶的entry。
     * 继承了LinkedHashMap.Entry，而LinkedHashMap.Entry<K,V> extends HashMap.Node<K,V> 。
     * 所以能用来被hashmap和LinkedHashMap使用，当做他们各自的通用的桶。
     */
    static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    	// node有 key，value， hash，next
    	// linkedlist的entry，增加了before，after
    	// TreeNode增加了 parent,left,right,prev,red
    	
        TreeNode<K,V> parent;  // 红黑树的连接
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // 在删除时，删除next时需要
        boolean red; // 默认为false
        TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
        }

        /**
         * 返回包含这个节点的树的根节点
         */
        final TreeNode<K,V> root() {
            for (TreeNode<K,V> r = this, p;;) {
            	// 不断parent，直到parent为null
                if ((p = r.parent) == null)
                    return r;
                r = p;
            }
        }

        /**
         * 保证给定的root是它的桶的第一个节点。
         */
        static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
            int n;
            // 将tab.length赋值给n
            if (root != null && tab != null && (n = tab.length) > 0) {
            	// 将(n - 1) & root.hash赋值给index，即root所处的桶的index
                int index = (n - 1) & root.hash;
                // 将tab[index]赋值给first
                TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
                // 如果first和root不同
                if (root != first) {
                    Node<K,V> rn;
                    // 将root赋值给tab[index] （原来是first）
                    tab[index] = root;
                    // 将root.prev赋值给rp
                    TreeNode<K,V> rp = root.prev;
                    // 将root.next赋值给rn
                    // 如果rn不为null，将rp（root.prev）赋值给rn（root.next）.prev
                    if ((rn = root.next) != null)
                        ((TreeNode<K,V>)rn).prev = rp;
                    // 如果rp（root.prev）不为null，将rn（root.next）赋值给rp（root.prev）.next
                    if (rp != null)
                        rp.next = rn;
                    // 如果first（tab[index]）不为null，将root赋值给first（tab[index]）.prev
                    if (first != null)
                        first.prev = root;
                    // 将first赋值给root.next，null赋值给root.prev
                    root.next = first;
                    root.prev = null;
                    // 即原来  tab[i]:   first             某个位置：  root.prev root  root.next
                    // 现在      tab[i]:   root  first       某个位置： root.prev  root.next
                }
                // 校验root
                assert checkInvariants(root);
            }
        }

        /**
         * 使用给定的hash和key，从root p（就是TreeNode自己）开始找节点。
         * kc参数在第一次使用比较键时缓存comparableClassFor(key)。
         * 先比较hash，如果hash相同，比较key，如果key不同，然后得到key对应的comparableClass，进行比较，
         * 如果比较结果相同，或者不能比较，对右孩子和左孩子依次调用find方法
         * （相当于对红黑树的下一层进行遍历，如果hash都相同，key都不能比较或者比较结果相同，相当于对整个红黑树遍历）
         */
        final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
        	// 把自己赋值给p
            TreeNode<K,V> p = this;
            // 从p开始，不断循环向下，找到对应节点
            do {
                int ph, dir; K pk;
                // p的左节点赋值给pl，右节点赋值给pr
                TreeNode<K,V> pl = p.left, pr = p.right, q;
                // 将p的hash赋值给ph
                // 根据ph与h的大小，如果不同，将pl或者pr赋值给p
                if ((ph = p.hash) > h)
                    p = pl;
                else if (ph < h)
                    p = pr;
                // 如果hash相同，将p的key赋值给pk
                // 如果pk与k相同，返回p
                else if ((pk = p.key) == k || (k != null && k.equals(pk)))
                    return p;
                // 如果pk与k不同，pl为null，pr赋值给p
                else if (pl == null)
                    p = pr;
                // 如果pk与k不同，pl不为null，pr为null，pl赋值给p
                else if (pr == null)
                    p = pl;
                // 如果pk与k不同，pl和pr不为null
                // 先根据kc或者k得到比较的类
                // 根据k与pk的比较关系，将pl或者pr赋值给p
                else if ((kc != null ||
                          (kc = comparableClassFor(k)) != null) &&
                         (dir = compareComparables(kc, k, pk)) != 0)
                    p = (dir < 0) ? pl : pr;
                // 如果k是不能比较的，或者p与pk比较结果相同
                // 对pr调用find，返回结果q
                // 如果在pr那里没找到，pl赋值给p
                else if ((q = pr.find(h, k, kc)) != null)
                    return q;
                else
                    p = pl;
            } while (p != null);
            return null;
        }

        /**
         * 对this的root节点，调用find方法,返回对应的节点。
         */
        final TreeNode<K,V> getTreeNode(int h, Object k) {
        	// 对这个节点调用root方法，得到这个节点的root，调用find，从根里去找h和k
            return ((parent != null) ? root() : this).find(h, k, null);
        }

        /**
         * 当hashcode相同，但是不可比较时，用于排序插入的断开连接功能。
         * 我们不需要一个总顺序，只需要一个一致的插入规则来在重新平衡之间保持等价。断开连接比必要的更能简化测试。
         * 先比较null，再比较className，最后比较Object类默认的hashcode.
         */
        static int tieBreakOrder(Object a, Object b) {
            int d;
            // 如果a或者b为null，直接返回0
            if (a == null || b == null ||
            	// 返回a的class与b的class名字的比较结果		
                (d = a.getClass().getName().
                 compareTo(b.getClass().getName())) == 0)
            	// 如果类的名字的比较结果相同
            	// 比较a与b的Object类默认的hashcode方法比较的结果，返回-1或1
                d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
                     -1 : 1);
            return d;
        }

        /**
         * 形成，与这个节点连接的一堆节点，构造成，的树，
         * 
         * @return root of tree
         */
        final void treeify(Node<K,V>[] tab) {
            TreeNode<K,V> root = null;
            // 将自己赋值给x
            // 对x进行循环，不断x=x.next，将每个next添加到树中
            for (TreeNode<K,V> x = this, next; x != null; x = next) {
            	// 将x.next赋值给next
                next = (TreeNode<K,V>)x.next;
                // 将null赋值给x的left与right
                x.left = x.right = null;
                if (root == null) {
                	//如果root为null
                	// null设置给x的parent，false设置给x的red（为黑）
                	// x设置给root
                    x.parent = null;
                    x.red = false;
                    root = x;
                }
                else {
                	// root不为null
                	// x的key赋值给k，x的hash赋值给h
                    K k = x.key;
                    int h = x.hash;
                    Class<?> kc = null;
                    // root赋值给p
                    for (TreeNode<K,V> p = root;;) {
                        int dir, ph;
                        // p的key赋值给pk
                        K pk = p.key;
                        // dir为p与x的hash与key比较的结果
                        if ((ph = p.hash) > h)
                            dir = -1;
                        else if (ph < h)
                            dir = 1;
                        else if ((kc == null &&
                                  (kc = comparableClassFor(k)) == null) ||
                                 (dir = compareComparables(kc, k, pk)) == 0)
                            dir = tieBreakOrder(k, pk);
                        // p赋值给xp
                        TreeNode<K,V> xp = p;
                        // 根据dir，将p.left或者right赋值给p
                        if ((p = (dir <= 0) ? p.left : p.right) == null) {
                            x.parent = xp;
                            if (dir <= 0)
                                xp.left = x;
                            else
                                xp.right = x;
                            root = balanceInsertion(root, x);
                            break;
                        }
                    }
                }
            }
            moveRootToFront(tab, root);
        }

        /**
         * 返回一个不是TreeNode的节点，这个节点连着的节点代替了之前的TreeNode
         */
        final Node<K,V> untreeify(HashMap<K,V> map) {
            Node<K,V> hd = null, tl = null;
            for (Node<K,V> q = this; q != null; q = q.next) {
            	// return new Node<>(p.hash, p.key, p.value, next);
            	// 将q转换为普通的节点，赋值给p
                Node<K,V> p = map.replacementNode(q, null);
                // tl为队尾，hd为队头
                if (tl == null) 
                	// 设置队头hd为p
                    hd = p;
                else
                	// 不断队尾tl.next为p
                    tl.next = p;
                tl = p;
            }
            // 返回队头hd
            return hd;
        }

        /**
         * 树版本的putVal。
         * 会在树中插入一个新节点，或者将原有节点返回，在putVal里面对它的value进行修改
         */
        final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
                                       int h, K k, V v) {
            Class<?> kc = null;
            boolean searched = false;
            
            // p = tab[i = (n - 1) & hash]
            // ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            // p是这个hash对应tab里的桶，也就是自己this
            
            // root为自己这个节点的root节点
            TreeNode<K,V> root = (parent != null) ? root() : this;
            // 将root赋值给p
            // 下面for的大循环的目的是，从root开始，根据hash和key，不断向下，遍历孩子，
            // 直到找到对应节点，或者对应节点没有，插入节点并维持红黑树平衡
            for (TreeNode<K,V> p = root;;) {
                int dir, ph; K pk;
                
                // 下面的那个大if，是为了得到dir，确定下次迭代时，p=p.left/right
                // 大if中，如果hash和key相同，直接返回p
                // 如果hash相同，key无法比较，调用find方法，如果找到，返回q
                
                // 将p的hash赋值给ph
                if ((ph = p.hash) > h)
                    dir = -1;
                else if (ph < h)
                    dir = 1;
                
                // 到这里ph与h相同
                // 将p的key赋值给pk
                // 如果找到key和hash对应的节点p，将p返回
                else if ((pk = p.key) == k || (k != null && k.equals(pk)))
                    return p;
                // 如果hash相同，key不同
                else if ((kc == null &&
                          (kc = comparableClassFor(k)) == null) ||
                		 // dir为k与pk比较的结果
                         (dir = compareComparables(kc, k, pk)) == 0) {
                	
                	// 如果比较结果为0
                    if (!searched) {
                        TreeNode<K,V> q, ch;
                        // 注意：由于searched的关系 直接调用find方法只会有一次！
                        searched = true;
                        // 对left和right调用find方法，如果找到了，返回对应节点
                        if (((ch = p.left) != null &&
                             (q = ch.find(h, k, kc)) != null) ||
                            ((ch = p.right) != null &&
                             (q = ch.find(h, k, kc)) != null))
                            return q;
                    }
                    // 如果hash相同，key不同，比较结果为0，find没找到，调用tieBreakOrder赋值给dir
                    // 即对两者的className和默认的hashcode进行依次比较
                    dir = tieBreakOrder(k, pk);
                }
                
                //上面的那个不断if else的语句结束，已经找到了节点或者得到了dir

                // p赋值给xp
                TreeNode<K,V> xp = p;
                // 根据dir，p=p.left/right
                // 但是如果赋值后p为null，代表没有找到对应节点，新增一个节点，并维持平衡
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                	// xp.next赋值给xpn
                    Node<K,V> xpn = xp.next;
                    //  return new TreeNode<>(hash, key, value, next);
                    // 根据hash，key，value，xpn新建一个TreeNode给x
                    TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
                    // 根据dir，将xp（原来的p）.left/right赋值给x
                    if (dir <= 0)
                        xp.left = x;
                    else
                        xp.right = x;
                    // 设置xp.next为x
                    xp.next = x;
                    // 设置x.parent和x.prev为xp
                    x.parent = x.prev = xp;
                    // 如果xpn不为null，设置xpn.prev=x
                    if (xpn != null)
                        ((TreeNode<K,V>)xpn).prev = x;
                    // 先设置孩子关系，xp.left/right = x ， x.parent = xp
                    // 然后设置双向链表的前后关系
                    // 原来 xp   xpn
                    // 现在 xp  x  xpn
                    // xp为x的父节点
                    
                    // 先维持插入x后的平衡
                    // 然后将平衡后的红黑树的新的root节点放到tab的最开始
                    moveRootToFront(tab, balanceInsertion(root, x));
                    return null;
                }
            }
        }

        /**
         * 删除给定的节点（就是this），那个节点必须在这次调用前存在。
         * 这比典型的红黑树删除节点更加混乱，因为我们因为我们不能使用由“next”指针固定的叶子后续来交换内部节点的内容，
         * 而“next”指针在遍历过程中是可独立访问的。
         * 所以，替代地，我们交换树的连接顺序。
         * 如果当前的树看上去有着过少的节点，桶被转换为普通的桶。（触发条件是2-6个节点间，取决于树的结构）
         */
        final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
                                  boolean movable) {
            int n;
            // 如果tab为null或者长度为0，则直接返回
            // tab.length赋值给n
            if (tab == null || (n = tab.length) == 0)
                return;
            // index为hash对应的桶的index
            int index = (n - 1) & hash;
            // tab[index]赋值给first
            // first赋值给root
            TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
            
            // 删除有两个部分，一个是对节点的next和prev关系的删除
            // 一个是对节点parent和孩子关系的删除
            
            // 步骤1：下面先对节点的next和prev关系的删除
            // this为被删除的节点
            // this.next赋值给succ
            // this.prev赋值给pred
            // 前后关系 pred this succ
            TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
            
            // 这个if，设置pred的next
            if (pred == null)
            	// 如果没有prev，将succ赋值给first，再赋值给tab[index]，相当于跳过this
                tab[index] = first = succ;
            else
            	// 有prev，succ赋值给pred.next
                pred.next = succ;
            
            // 这个if，设置succ的prev
            if (succ != null)
            	// 如果有next，pred赋值给succ.prev
                succ.prev = pred;
            
            // 如果first为null，即代表succ和pred都是null，直接将这个桶设置为null，即可，已经做了，就直接返回
            if (first == null)
                return;
            
            // 将root的根节点赋值给root
            if (root.parent != null)
                root = root.root();
            
            // 步骤2：如果root，root的right或left，root的left的left，有一个为null，
            // 说明红黑树太稀疏了，反树化，调用first.untreeify(map)，赋值给tab[index]，然后返回
            // root.left赋值给rl
            if (root == null || root.right == null ||
                (rl = root.left) == null || rl.left == null) {
                tab[index] = first.untreeify(map);  // too small
                return;
            }
            
            // 步骤3：判断树节点的情况
            //  p = tab[index = (n - 1) & hash]
            //  node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            //  ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            // this是hash对应的桶下，对应的key对应的节点，然后对它调用removeTreeNode方法
            // this赋值给p，left赋值给pl，right赋值给pr
            TreeNode<K,V> p = this, pl = left, pr = right, replacement;
            if (pl != null && pr != null) {
            	// 如果pl和pr都不为null
            	// pr赋值给s
                TreeNode<K,V> s = pr, sl;
                // 将s最最左孩子赋值给s（即被删除节点的右孩子的最最左孩子）
                while ((sl = s.left) != null) // find successor
                    s = sl;
                // 步骤3.1：将s和p的颜色转换
                boolean c = s.red; s.red = p.red; p.red = c; // swap colors
                // s.right赋值给sr
                TreeNode<K,V> sr = s.right;
                // p.parent赋值给pp
                TreeNode<K,V> pp = p.parent;
                
                // 步骤3.2 设置p和s以及它们的孩子，父亲间的关系
                if (s == pr) { // p was s's direct parent
                	// 如果s和pr相同，代表p的右孩子是s，而且s没有左孩子，p是s的父亲
                	// 设置p.parent为s，s.right为p，互换父子关系
                    p.parent = s;
                    s.right = p;
                }
                else {
                	// p不是s的父亲，s.parent赋值给sp
                    TreeNode<K,V> sp = s.parent;
                    // sp赋值给p.parent                    
                    if ((p.parent = sp) != null) {
                    	// 如果sp不为null，设置sp的left/right为p
                        if (s == sp.left)
                            sp.left = p;
                        else
                            sp.right = p;
                    }
                    // pr赋值给s.right
                    if ((s.right = pr) != null)
                    	// 如果pr不为null，设置pr.parent为s
                        pr.parent = s;
                }
                // 步骤3.3：设置p，sr，pl，
                // 设置p.left为null
                p.left = null;
                // 设置p.right为sr
                if ((p.right = sr) != null)
                	// 如果sr不为null，设置sr.parent为null
                    sr.parent = p;
                // 设置s.left为pl
                if ((s.left = pl) != null)
                	// 如果pl不为null，设置pl.parent为s
                    pl.parent = s;
                // 设置s.parent为pp
                if ((s.parent = pp) == null)
                	// 如果pp为null，设置root为s
                    root = s;
                // 如果pp不为null，设置pp.left/right为s
                else if (p == pp.left)
                    pp.left = s;
                else
                    pp.right = s;
                // 如果sr不为null，设置replacement为sr，否则为p
                if (sr != null)
                    replacement = sr;
                else
                    replacement = p;
            }
            // 如果p只有左孩子，replacement = pl
            // 如果p只有右孩子，replacement = pr
            // 如果p没有孩子，replacement = p            
            else if (pl != null)
                replacement = pl;
            else if (pr != null)
                replacement = pr;
            else
                replacement = p;
            
            if (replacement != p) {
            	// 如果replacement不为p，即p有左或右孩子，或者sr为null
            	// 设置replacement.parent = p.parent
            	// 设置pp为p.parent
                TreeNode<K,V> pp = replacement.parent = p.parent;
                if (pp == null)
                	// 如果pp为null，设置root为replacement
                    root = replacement;
                // 否则，设置pp.left/right为replacement
                else if (p == pp.left)
                    pp.left = replacement;
                else
                    pp.right = replacement;
                // p的left，right，parent都设置为null
                p.left = p.right = p.parent = null;
            }

            // 如果p为红色，则删除即可，r为root节点
            // 如果p为黑色，删除影响平衡，调用balanceDeletion，r为返回的节点
            TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);

            if (replacement == p) {  // detach
            	// 如果replacement为p
            	// 设置pp为p.parent
                TreeNode<K,V> pp = p.parent;
                // 设置p的parent为null
                p.parent = null;
                if (pp != null) {
                	// 设置pp的left/right为null
                    if (p == pp.left)
                        pp.left = null;
                    else if (p == pp.right)
                        pp.right = null;
                }
            }
            // 一般movable为true
            if (movable)
            	// 将r变成tab的桶节点
                moveRootToFront(tab, r);
        }

        /**
         * 将一个树桶的节点分割为低位和高位的树桶，或者如果当前的太小了，反树化。
         * 仅仅当resize时调用，看上面关于分割的位的讨论。
         *
         * @param map the map
         * @param tab the table for recording bin heads
         * @param index the index of the table being split
         * @param bit the bit of hash to split on
         */
        final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
            TreeNode<K,V> b = this;
            // Relink into lo and hi lists, preserving order
            TreeNode<K,V> loHead = null, loTail = null;
            TreeNode<K,V> hiHead = null, hiTail = null;
            int lc = 0, hc = 0;
            // oldTab[j]赋值给e
            // ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
            // 设置e为b，也就是this，也就是树桶的第一个节点
            // 从e开始，不断e.next进行循环
            for (TreeNode<K,V> e = b, next; e != null; e = next) {
                next = (TreeNode<K,V>)e.next;
                // 设置e.next为null
                e.next = null;
                // bit就是oldCap，二进制位10000
                // 如果hash&bit为0，放在lo的队尾,lc++
                if ((e.hash & bit) == 0) {
                    if ((e.prev = loTail) == null)
                        loHead = e;
                    else
                        loTail.next = e;
                    loTail = e;
                    ++lc;
                }
                // 如果hash&bit为1，放在hi的队尾,hc++
                else {
                    if ((e.prev = hiTail) == null)
                        hiHead = e;
                    else
                        hiTail.next = e;
                    hiTail = e;
                    ++hc;
                }
            }

            if (loHead != null) {
                if (lc <= UNTREEIFY_THRESHOLD)
                	// 如果lc<=6，tab[index]为loHead的反树化结果
                    tab[index] = loHead.untreeify(map);
                else {
                	// 如果lc>6,tab[index] = loHead
                    tab[index] = loHead;
                    if (hiHead != null) // (else is already treeified)
                    	// 如果hiHead不为null，树化loHead
                        loHead.treeify(tab);
                }
            }
            if (hiHead != null) {
                if (hc <= UNTREEIFY_THRESHOLD)
                	// 如果hc<=6，tab[index + bit]为hiHead的反树化结果
                    tab[index + bit] = hiHead.untreeify(map);
                else {
                	// 如果hc>6,tab[index + bit] = hiHead
                    tab[index + bit] = hiHead;
                    if (loHead != null)
                    	// 如果loHead不为null，树化hiHead
                        hiHead.treeify(tab);
                }
            }
        }

        /* ------------------------------------------------------------ */
        // Red-black tree methods, all adapted from CLR

        // 左旋操作，其中root为根节点，p为当前节点，r为p的右节点，rl为r的左节点，pp为p的父节点
        // 左旋之后，r替换p的位置，rl挪到p的右节点
        // 节点位置变换之后，既要改变其父节点的left/right值，也要改变当前节点中parent的值，
        // 改变是双向的，父子均有指向，改变之后均要修改
        static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
                                              TreeNode<K,V> p) {
            TreeNode<K,V> r, pp, rl;
            if (p != null && (r = p.right) != null) {
                if ((rl = p.right = r.left) != null)
                    rl.parent = p;
                if ((pp = r.parent = p.parent) == null)
                    (root = r).red = false;
                else if (pp.left == p)
                    pp.left = r;
                else
                    pp.right = r;
                r.left = p;
                p.parent = r;
            }
            return root;
        }

        static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
                                               TreeNode<K,V> p) {
            TreeNode<K,V> l, pp, lr;
            if (p != null && (l = p.left) != null) {
                if ((lr = p.left = l.right) != null)
                    lr.parent = p;
                if ((pp = l.parent = p.parent) == null)
                    (root = l).red = false;
                else if (pp.right == p)
                    pp.right = l;
                else
                    pp.left = l;
                l.right = p;
                p.parent = l;
            }
            return root;
        }

        static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
                                                    TreeNode<K,V> x) {
            x.red = true;
            for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
                if ((xp = x.parent) == null) {
                    x.red = false;
                    return x;
                }
                else if (!xp.red || (xpp = xp.parent) == null)
                    return root;
                if (xp == (xppl = xpp.left)) {
                    if ((xppr = xpp.right) != null && xppr.red) {
                        xppr.red = false;
                        xp.red = false;
                        xpp.red = true;
                        x = xpp;
                    }
                    else {
                        if (x == xp.right) {
                            root = rotateLeft(root, x = xp);
                            xpp = (xp = x.parent) == null ? null : xp.parent;
                        }
                        if (xp != null) {
                            xp.red = false;
                            if (xpp != null) {
                                xpp.red = true;
                                root = rotateRight(root, xpp);
                            }
                        }
                    }
                }
                else {
                    if (xppl != null && xppl.red) {
                        xppl.red = false;
                        xp.red = false;
                        xpp.red = true;
                        x = xpp;
                    }
                    else {
                        if (x == xp.left) {
                            root = rotateRight(root, x = xp);
                            xpp = (xp = x.parent) == null ? null : xp.parent;
                        }
                        if (xp != null) {
                            xp.red = false;
                            if (xpp != null) {
                                xpp.red = true;
                                root = rotateLeft(root, xpp);
                            }
                        }
                    }
                }
            }
        }

        static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
                                                   TreeNode<K,V> x) {
            for (TreeNode<K,V> xp, xpl, xpr;;)  {
                if (x == null || x == root)
                    return root;
                else if ((xp = x.parent) == null) {
                    x.red = false;
                    return x;
                }
                else if (x.red) {
                    x.red = false;
                    return root;
                }
                else if ((xpl = xp.left) == x) {
                    if ((xpr = xp.right) != null && xpr.red) {
                        xpr.red = false;
                        xp.red = true;
                        root = rotateLeft(root, xp);
                        xpr = (xp = x.parent) == null ? null : xp.right;
                    }
                    if (xpr == null)
                        x = xp;
                    else {
                        TreeNode<K,V> sl = xpr.left, sr = xpr.right;
                        if ((sr == null || !sr.red) &&
                            (sl == null || !sl.red)) {
                            xpr.red = true;
                            x = xp;
                        }
                        else {
                            if (sr == null || !sr.red) {
                                if (sl != null)
                                    sl.red = false;
                                xpr.red = true;
                                root = rotateRight(root, xpr);
                                xpr = (xp = x.parent) == null ?
                                    null : xp.right;
                            }
                            if (xpr != null) {
                                xpr.red = (xp == null) ? false : xp.red;
                                if ((sr = xpr.right) != null)
                                    sr.red = false;
                            }
                            if (xp != null) {
                                xp.red = false;
                                root = rotateLeft(root, xp);
                            }
                            x = root;
                        }
                    }
                }
                else { // symmetric
                    if (xpl != null && xpl.red) {
                        xpl.red = false;
                        xp.red = true;
                        root = rotateRight(root, xp);
                        xpl = (xp = x.parent) == null ? null : xp.left;
                    }
                    if (xpl == null)
                        x = xp;
                    else {
                        TreeNode<K,V> sl = xpl.left, sr = xpl.right;
                        if ((sl == null || !sl.red) &&
                            (sr == null || !sr.red)) {
                            xpl.red = true;
                            x = xp;
                        }
                        else {
                            if (sl == null || !sl.red) {
                                if (sr != null)
                                    sr.red = false;
                                xpl.red = true;
                                root = rotateLeft(root, xpl);
                                xpl = (xp = x.parent) == null ?
                                    null : xp.left;
                            }
                            if (xpl != null) {
                                xpl.red = (xp == null) ? false : xp.red;
                                if ((sl = xpl.left) != null)
                                    sl.red = false;
                            }
                            if (xp != null) {
                                xp.red = false;
                                root = rotateRight(root, xp);
                            }
                            x = root;
                        }
                    }
                }
            }
        }

        /**
         * 递归不变量检查
         */
        static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
        	// tp为parent，tl为left，tr为right
            TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,
            // rb为prev，tn为next		
                tb = t.prev, tn = (TreeNode<K,V>)t.next;
            // 校验prev的next
            if (tb != null && tb.next != t)
                return false;
            // 校验next的prev
            if (tn != null && tn.prev != t)
                return false;
            // 校验parent的子孩子
            if (tp != null && t != tp.left && t != tp.right)
                return false;
            // 校验left的父亲，并且parent的hash要大于left的hash
            if (tl != null && (tl.parent != t || tl.hash > t.hash))
                return false;
            // 校验right的父亲，并且parent的hash要小于right的hash
            if (tr != null && (tr.parent != t || tr.hash < t.hash))
                return false;
            // 如果自己，left，right都为红色，就错了
            if (t.red && tl != null && tl.red && tr != null && tr.red)
                return false;
            // 递归校验left和right
            if (tl != null && !checkInvariants(tl))
                return false;
            if (tr != null && !checkInvariants(tr))
                return false;
            return true;
        }
    }

}
